struct Barrett {
  using u32 = unsigned int;
  using u64 = unsigned long long;
  using u128 = unsigned __int128_t;
  static constexpr u128 s = u128(1) << 96;

  Barrett(const u32 P) : p_(P), m_((s - 1) / P + 1){}

  u32 div(const u64 &v) const {
    return (v * m_) >> 96;
  }

  u32 operator()(u64 v) {
    return v - u64(div(v)) * p_;
  }

  u128 m_;
  u32 p_;
};
// MAX_LEN should be a prime number
static constexpr int MAX_LEN = 2120009;
static Barrett fast_mod(MAX_LEN);

template<class Key, class Value, class Hash>
struct HashMap {
  using u64 = unsigned long long;
public:
  HashMap() : total_(0), size_(0) {}

  void clear() {
    total_ = size_ = 0;
    for (auto &p : pos_) {
      head_[p] = -1;
    }
    pos_.clear();
  }
  
  bool find(const Key &key) {
    int p = fast_mod(static_cast<u64>(hash_(key)));
    if (!head_[p]) {
      return false;
    }
    for (int i = head_[p]; i; i = next_[i]) {
      if (keys_[i] == key) {
        return true;
      }
    }
    return false;
  }

  void insert(const Key &key, const Value &value) {
    if (find(key)) {
      return;
    }
    int p = fast_mod(static_cast<u64>(hash_(key)));
    next_[++total_] = head_[p];
    head_[p] = total_;
    keys_[total_] = key;
    values_[total_] = value;
    pos_.emplace_back(p);
    size_++;
  }

  bool erase(const Key &key) {
    int p = fast_mod(static_cast<u64>(hash_(key)));
    if (!head_[p]) {
      return false;
    }
    for (int i = head_[p], j; i; i = next_[i]) {
      if (keys_[i] == key) {
        if (i == head_[p]) {
          head_[p] = next_[i];
        } else {
          next_[j] = next_[i];
        }
        size_--;
        return true;
      }
      j = i;
    }
    return false;
  }

  int size() const {
    return size_;
  }

  Value &operator[](const Key &key) {
    int p = fast_mod(static_cast<u64>(hash_(key)));
    if (!head_[p]) {
      pos_.emplace_back(p);
    }
    for (int i = head_[p]; i; i = next_[i]) {
      if (keys_[i] == key) {
        return values_[i];
      }
    }
    insert(key, Value());
    return values_[total_];
  }
private:
  std::vector<int> pos_;
  int head_[MAX_LEN], next_[MAX_LEN], total_, size_;
  Key keys_[MAX_LEN];
  Value values_[MAX_LEN];
  Hash hash_;
};
// MyHash如果需要对不是整数外的hash，则需要自定义实现split函数以及operator
struct MyHash {
  using u64 = unsigned long long;
  using u32 = unsigned int;

	static u64 split(u64 x) {
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
  }

	int operator()(const u64 &x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return fast_mod(static_cast<u64>(split(x + FIXED_RANDOM)));
	}
};
// HashMap<int, int, std::hash<int>> mp;
HashMap<unsigned long long, int, MyHash> mp;